package com.dong.ListNode.arithemtic;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author dcz
 * @classname RemoveNthFromEnd
 * @description 删除链表的倒数第n个节点
 * @date 2022/4/12 8:48
 */
public class RemoveNthFromEnd {

    //双指针法
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //虚拟节点
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        //慢指针
        ListNode slow = dummy;
        ListNode fast = head;

        //这一步很精髓，先让快指针相对于慢指针走n+1步
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        //当fast=null时，slow指针走到了待删除元素的前一个
        while (fast!=null){
            fast = fast.next;
            slow = slow.next;
        }
        //删除节点
        slow.next = slow.next.next;
        return dummy.next;
    }

    //利用栈来解
    public ListNode removeNthFromEnd2(ListNode head, int n) {
        ListNode dunmy = new ListNode(0, head);
        Deque<ListNode> stack = new LinkedList<>();
        ListNode cur = dunmy;
        //所有的元素压入栈
        while (cur!=null){
            stack.push(cur);
             cur = cur.next;
        }
        //逆向出栈，直到要删除元素的前一个
        while (n-->0){
            stack.pop();
        }
        ListNode prev = stack.peek();
        prev.next = prev.next.next;
        ListNode node = dunmy.next;
        return node;
    }

}
